package algorithm.weightgraph;

import algorithm.unionfind.UnionFind;
import algorithm.unionfind.UnionFindRank;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class LazyPrimMST<Weight extends Number&Comparable> {

    //是否已访问过
    private boolean[] visited;

    private Graph<Weight> graph;

    private MinHeap<Edge<Weight>> minHeap;

    private List<Edge<Weight>> mst;

    private Number mstWeight;

    public LazyPrimMST(Graph graph){
        this.graph = graph;
        this.visited = new boolean[graph.getPointNums()];
        this.minHeap = new MinHeap(graph.getEdgeNums());
        this.mst = new LinkedList<>();
        getShortestPath(0);

        this.mstWeight = mst.get(0).getWeight();
        for (int i = 1; i < mst.size(); i++) {
            mstWeight= mstWeight.doubleValue()+mst.get(i).getWeight().doubleValue();
        }
    }


    private void getShortestPath(int s){
        if (visited[s]){
            return;
        }
        visited[s] = true;

        Iterator<Edge<Weight>> iterator = graph.getIterator(s);
        while (iterator.hasNext()){
            Edge<Weight> edge = iterator.next();
            //边的另一个点没有访问过
            if (!visited[edge.getE()]){
                minHeap.addItem(edge);
            }
        }
        while (minHeap.getCount()>0){
            Edge<Weight> edge = minHeap.exportMin();
            //边的两个点都没有访问过
            if (!visited[edge.getE()]){
                mst.add(edge);
                getShortestPath(edge.getE());
            }
        }

    }


    public List<Edge<Weight>> mst(){
        return this.mst;
    }


    public Number getWeight(){
        return mstWeight;
    }


    public static void main(String[] args) {
        Graph graph = ReadWeightGraph.readGraph(SparseWeightGraph.class, "testG1.txt");
        LazyPrimMST<Double> lazyPrimMST = new LazyPrimMST(graph);
        List<Edge<Double>> mst = lazyPrimMST.mst();
        Number weight = lazyPrimMST.getWeight();
        System.out.println(weight);
    }
}
